package com.example.lib5.sort.test;

import java.util.Arrays;

public class RadixSort {
    public static void main(String[] args) {
        int[] arr={53,3,542,748,14,214};
        System.out.println(Arrays.toString(arr));
        radixSortF(arr);
        System.out.println(Arrays.toString(arr));
    }

    private static void radixSort(int[] arr) {
        //中转的二维数组
        int[][] arrChange=new int[10][arr.length];
        //中转数组的每个位置数组的有效值个数，默认都是0
        int[] arrChangeValue=new int[10];
        //获取数组最大值，并获取最大长度
        int max=arr[0];
        for (int i = 0; i < arr.length; i++) {
            if (arr[i]>max){
                max=arr[i];
            }
        }
        int length = String.valueOf(max).length();

        //根据最大值，获取要循环的位数，然后放到二维数组
        for (int i = 0,n=1; i < length; i++,n*=10) {
            //获取个位数
            for (int j = 0; j < arr.length; j++) {
                int radix = arr[j]/n % 10;
                arrChange[radix][arrChangeValue[radix]++]=arr[j];
            }
            //从二维数组中取值放到arr
            int arrIndex=0;
            for (int k = 0; k < arrChange.length; k++) {
                if (arrChangeValue[k]!=0){
                    for (int l = 0; l < arrChangeValue[k]; l++) {
                        arr[arrIndex++]=arrChange[k][l];
                    }
                    arrChangeValue[k]=0;
                }
            }

        }

    }
    private static void radixSortC(int[] arr) {
        //中转数组，中转数组每个数组的个数
        int[][] arrChange=new int[10][arr.length];
        int[] arrChangeCount=new int[10];
        //获取数组的最大值得长度
        int max=arr[0];
        for (int i = 0; i < arr.length; i++) {
            if (max<arr[i]){
                max=arr[i];
            }
        }
        int length = String.valueOf(max).length();
        for (int i = 0,n=1; i < length; i++,n*=10) {
            //遍历数组放到二维数组
            for (int j = 0; j < arr.length; j++) {
                //第一次，获取个位数
                int value = arr[j]/n % 10;
                //放到二维数组
                arrChange[value][arrChangeCount[value]++]=arr[j];
            }
            //遍历二维数组，把值放到arr
            int arrIndex=0;
            for (int k = 0; k < arrChange.length; k++) {
                if (arrChangeCount[k]!=0){
                    for (int l = 0; l < arrChangeCount[k]; l++) {
                        arr[arrIndex++]=arrChange[k][l];
                    }
                    arrChangeCount[k]=0;
                }
            }
        }
    }
    private static void radixSortD(int[] arr) {
        //获取最大值的长度
        int max=arr[0];
        for (int i = 1; i < arr.length; i++) {
            if (arr[i]>max) {
                max=arr[i];
            }
        }
        int length = String.valueOf(max).length();
        //中转二维数组，中转二维数组的每组个数
        int[][] bucket=new int[10][arr.length];
        int[] bucketElementCount=new int[10];
        for (int i = 0,n=1; i < length; i++,n*=10) {
            //循环把数组取出来放到中转数组
            for (int j = 0; j < arr.length; j++) {
                int digitOfElement = arr[j] / n % 10;
                bucket[digitOfElement][bucketElementCount[digitOfElement]]=arr[j];
                bucketElementCount[digitOfElement]++;
            }
            //把中转数组放到原来的数组
            int arrIndex=0;
            for (int k = 0; k < bucket.length; k++) {
                if (bucketElementCount[k]>0){
                    for (int l = 0; l < bucketElementCount[k]; l++) {
                        arr[arrIndex]=bucket[k][l];
                        arrIndex++;
                    }
                    bucketElementCount[k]=0;
                }
            }
            System.out.println(Arrays.toString(arr));
        }



    }
    private static void radixSortF(int[] arr) {
        //获取arr的最大值得最大长度
        int max=arr[0];
        for (int i = 1; i < arr.length; i++) {
            if (max<arr[i]){
                max=arr[i];
            }
        }
        int length = String.valueOf(max).length();

        //辅助数组级辅助数组的对应位置的个数
        int[][]  changeArr=new int[10][arr.length];
        int[] changeArrCount=new int[10];

        /**
         * for几轮遍历
         */
        for (int i = 0,n=1; i < length; i++,n*=10) {
            //获取对应位的位置的对应值
            for (int j = 0; j < arr.length; j++) {
                int indexValue = arr[j] / n % 10;
                //从数组拿出数据,放到转移数组
                changeArr[indexValue][changeArrCount[indexValue]++]=arr[j];
            }
            //再从转移数组中放回数组
            int index=0;
            for (int k = 0; k < 10; k++) {
                if (changeArrCount[k]!=0) {
                    for (int l = 0; l < changeArrCount[k]; l++) {
                        arr[index++]=changeArr[k][l];
                    }
                    changeArrCount[k]=0;
                }
            }
            System.out.println(Arrays.toString(arr));
        }

    }
}
